package wtx.geek;

import java.util.*;
import java.util.Random;


/**
You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
algorithm to find the maximum sub sequence which has equal number of 1s and
0s.

Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself

2)1101000
The longest sub sequence that satisfies the problem is 110100

 Link: https://careercup.com/question?id=3576940

 The following solution assumes that the given array is an integer array (instead of a char array) for ease of exposition.
 Later, we will show how we can modify it to use a char array instead.

 The outline of the solution:
 1) Transform the (integer) array (modify in place) to an equivalent (integer) array
 2) Perform computation on the array
 3) Restore array.
 So, in effect you would have used only O(1) additional space.

 We shall cheat a little bit and use indexing in the range [0...n] instead of [0...n-1].
 We assume that the given (integer) array actually occupies indices [1...n]. This makes things easier to understand.
 At the end, this will be irrelevant.

 Step 1(transformation):
 A[i] = (i==0)?0:((A[i]==0?1:-1) + A[i-1])
 In words, A[i] = (number of zeroes - number of ones) in the first i places of the (original) array. At the end of step 1,
 you have an array of integers. The task is to find out
 max{y-x | A[y] = A[x] }


 Notation:
 First(t) = min{ x | A[x] = t} if t appears in A, infinity if t doesn't appear in A
 Last(t) = max{ x | A[x] = t} if t appears in A, -infinity if t doesn't appear in A
 D(t) = Last(t) - First(t)
 L = max{ D(t) | integer t}

 First and Last correspond to the indices of the first and last occurences respectively of their argument.
 We call integer T good if D(T) = L. Our task is to compute L. If we identify *one* good integer, g, then,
 we can compute L = D(g) in linear time(trivially), with O(1) additional space.
 **/

public class Solution {
  public static int[] findLongestEqualSubrange(int[] array) {
    final int len = array.length;
    int[] array2 = new int[len+1];
    array2[0] = 0;
    for (int i = 1; i <= len; ++i) {
      array2[i] = array2[i-1] + (array[i-1] == 0 ? 1 : -1);
    }
    Map<Integer, Integer> firstOccur = new HashMap<>(),
            lastOccur = new HashMap<>();
    int maxLen = 0;
    int left = -1, right = -1;
    Set<Integer> usedEle = new HashSet<>();
    for (int i = 0; i <= len; ++i) {
      int ele = array2[i];
      firstOccur.putIfAbsent(ele, i);
      int ele2 = array2[len - i];
      lastOccur.putIfAbsent(ele2, len - i);
    }

    for (int i = 0; i <= len; ++i) {
      int ele = array2[i];
      if (!usedEle.contains(ele) && lastOccur.containsKey(ele)) {
        int lenRange = lastOccur.get(ele) - firstOccur.get(ele);
        if (lenRange > maxLen) {
          maxLen = lenRange;
          left = i;
          right = lastOccur.get(ele);
        }
        usedEle.add(ele);
      }
      if (maxLen > len-i) {
        break;
      }
    }
    int[] array_out = new int[right-left];
    for (int i = 0; i < maxLen; ++i) {
      array_out[i] = array[i+left];
    }
    return array_out;
  }

  public static int[] findLongestEqualSubrangeNotWork(int[] array) {
    /**
     首先统计整个字符串的所有元素和sum，如果2*sum == len，则返回[0, len-1]
     如果2*sum < len，说明0多，需要找左右2边为0的删掉；如果两边都是1, 寻找左右2边距离0最近的一边进行删除
     另外一边和0的距离可以保存下来，方便下次使用。
     如果2*sum > len, 说明1多。采用和上面类似的方式进行处理
     */
    int len = array.length;
    int ones = 0, zeros;
    for (int i = 0; i < len; ++i) {
      ones += array[i];
    }
    zeros = len - ones;
    if (ones == zeros) {
      return array;
    }
    int leftOnes = 0, rightOnes = 0, leftZeros = 0, rightZeros = 0;
    int i = 0, j = len-1;
    while (i < len && j >= 0 && ones != zeros) {
      if (ones > zeros) {
        // remove extra ones
        if (array[i] == 1) {
          ++i;
          --ones;
        } else if (array[j] == 1) {
          --j;
          --ones;
        } else {
          if (leftZeros == 0) {
            while(i < j && array[i+leftZeros] == 0) {
              ++leftZeros;
            }
          }
          if (rightZeros == 0) {
            while(i < j && array[j-rightZeros] == 0) {
              ++rightZeros;
            }
          }
          if (leftZeros < rightZeros) {
            i += leftZeros;
            zeros -= leftZeros;
            leftZeros = 0;
          } else {
            j -= rightZeros;
            zeros -= rightZeros;
            rightZeros = 0;
          }
        }
      } else {
        // remove extra zeros
        if (array[i] == 0) {
          ++i;
          --zeros;
        } else if (array[j] == 0) {
          --j;
          --zeros;
        } else {
          if (leftOnes == 0) {
            while(i < j && array[i+leftOnes] == 1) {
              ++leftOnes;
            }
          }
          if (rightOnes == 0) {
            while(i < j && array[j-rightOnes] == 1) {
              ++rightOnes;
            }
          }
          if (leftOnes < rightOnes) {
            i += leftOnes;
            ones -= leftOnes;
            leftOnes = 0;
          } else {
            j -= rightOnes;
            ones -= rightOnes;
            rightOnes = 0;
          }
        }
      }
    }
    if (ones != zeros) {
      return null;
    }
    int k = 0;
    int[] ret = new int[j-i+1];
    for (; i <= j; ++i) {
      ret[k++] = array[i];
    }
    return ret;
  }

  public static void main(String[] args) {
    int[] array = {0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0};
    int[] range = findLongestEqualSubrange(array);
    StringJoiner sj = new StringJoiner(", ");
    for (int i = 0; i < range.length; ++i) {
      sj.add(String.valueOf(range[i]));
    }
    System.out.println("longest zeros-ones range: " + sj.toString());
  }
}
